#include <cstdio>
#include <iostream>
#include <windows.h>
#include <queue>
#include <cstdlib>
#include <fstream>
#include <cstring>
#include "Cmd_Draw.h"
#include "List.h"
using namespace std;


#define MaxN  100010
#define MaxM  500010
#define INF 0x7fffffff

struct stationtype
{
    int iscross; // is cross between 
    int busline_num[100]; // if is bus busline number
    int metroline_num[100]; // if is metro metroline number

}station[MaxN];


struct edge
{
    int from, to, dis, next, top, sta, money;
}e[MaxM];
int head[MaxN], dis[MaxN], cnt;
int path[MaxN];
int n,s,line_total,bus_total,metro_total,searchtype;

LinkList buslist[100],metrolist[100];


void add_edge( int u, int v, int d, int m)
{
    cnt++;
    e[cnt].from=u;
    e[cnt].to = v;
    e[cnt].top = 0;
    e[head[u]].top = cnt;
    e[cnt].next = head[u];

    e[cnt].dis = d;
    e[cnt].sta = 1;
    e[cnt].money = m;

    head[u] = cnt;
}

void delete_edge(int arc)
{
    int up=e[arc].top, down=e[arc].next;
	if	(up == 0)	head[e[arc].from] = down;
	else e[up].next = down;	
	if	(down>0)	e[down].top = up;		
}

int find_edge(int u,int v)
{
    for(int i=head[u];i;i=e[i].next)
    {
        int y=e[i].to;
        if(y==v) return i;   
    }
    return 0;
}

int find_edge_dis(int u,int v)
{
    for(int i=head[u];i;i=e[i].next)
    {
        int y=e[i].to;
        if(y==v) return e[i].dis;   
    }
    return 0;
}


struct nodet
{
    int dis;
    int pos;

    bool operator <( const nodet &x )const
    {
       return x.dis < dis;
    }
};


inline void dijkstra()
{
    priority_queue<nodet> q;
    bool vis[MaxN]; memset(vis,0,sizeof(vis));
    dis[s] = 0;
    q.push( ( nodet ){0, s} );
    while( !q.empty() )
    {
        nodet tmp = q.top();
        q.pop();
        int x = tmp.pos, d = tmp.dis;
        if( vis[x] ) continue;
        vis[x] = 1;
        for( int i = head[x]; i; i = e[i].next )
        {
            int y = e[i].to;
            if(searchtype == 1)
            {
                if( dis[y] > dis[x] + e[i].dis )
                {
                    dis[y] = dis[x] + e[i].dis;
                    path[y]=x;
                    if( !vis[y] ) q.push( (nodet){dis[y], y} );
                }
            }
            else if(searchtype == 2)
            {
                if( dis[y] > dis[x] + e[i].sta )
                {
                    dis[y] = dis[x] + e[i].sta;
                    path[y]=x;
                    if( !vis[y] ) q.push( (nodet){dis[y], y} );
                }
            }
            else if(searchtype == 3)
            {
                if( dis[y] > dis[x] + e[i].money )
                {
                    dis[y] = dis[x] + e[i].money;
                    path[y]=x;
                    if( !vis[y] ) q.push( (nodet){dis[y], y} );
                }
            }
        }
    }
}

void find(int st, int x)	
{
	if (path[x] == 1) {
		cout << st;
	}
	else {
		find(st,path[x]);
	}
	cout << " -> " << x;
    if(station[x].iscross==1) cout<< "(Cross Station)";
	return;
}


int main()
{
    ifstream in;
    in.open("data/data.txt");
    if(!in.is_open()) 
    {
        cout<<"Open config file failed! Please check!"<<endl;
        Sleep(1000);
        return 0;
    }
    //if(freopen("C:\\Users\\Simon\\Desktop\\busline_inquiry\\data\\data.txt","r",stdin) == 0) cout<<"Open file failed!"<<endl; 
    in>>n>>line_total>>metro_total>>bus_total;
    // for bus money is 1 per station and for metro is half the distance
    for(int i=1;i<=metro_total;i++)
    {
        int station_num;in>>station_num;
        for(int j=1;j<=station_num;j++)
        {
            int station_id;in>>station_id;
            station[station_id].metroline_num[i] = 1;
            station[station_id].metroline_num[0] = 1;
            metrolist[i].Insert(j,station_id);
        }
    }
    for(int i=1;i<=bus_total;i++)
    {
        int station_num;in>>station_num;
        for(int j=1;j<=station_num;j++)
        {
            int station_id;in>>station_id;
            station[station_id].busline_num[i] = 1;
            station[station_id].busline_num[0] = 1;
            buslist[i].Insert(j,station_id);
        }
    }
    for(int i=1;i<=n;i++)
    {
        int tempcnt=0;
        for(int j=1;j<=metro_total;j++) 
        {
            if(station[i].metroline_num[j]) tempcnt++;
        }
        for(int j=1;j<=bus_total;j++) 
        {
            if(station[i].busline_num[j]) tempcnt++;
        }
        if(tempcnt>=2) station[i].iscross=1;
    }

    for(int i=1;i<=n;i++)
    {
        int num,vernum;
        in>>num>>vernum;
        for(int j=1;j<=vernum;j++)
        {
            int u,v,d;
            u=num;
            in>>v>>d;
            int temp_money;
            if(station[v].busline_num[0])  temp_money = 1;
            else if (station[v].metroline_num[0]) temp_money = (int)(d/2)+1;
            add_edge(u,v,d,temp_money);
            add_edge(v,u,d,temp_money);
        }
    }
    in.close();
    string inputstring;
    cout<<"Welcome to Virtual-BEIJING2022 Public Transportation Consultant and Management System - BTCMS "<<endl;
    for(int i=1;i<=6;i++) 
    {
        if((i+3)%3==1) Set_Grapics(0,1,7),cout<<"Initiating .   "<<endl;
        if((i+3)%3==2 )Set_Grapics(0,1,7),cout<<"Initiating ..  "<<endl;
        if((i+3)%3==0) Set_Grapics(0,1,7),cout<<"Initiating ... "<<endl;
        Sleep(400);
    }
    bool checktag=0;
    while(1)
    {
        Clear_Grapics();
       
        cout<<"If you want to manage  the transport line,  please input manage "<<endl;
        cout<<"If you want to inquire the transport line,  please input inquire"<<endl;
        cout<<"If you want to exit    the transport line,  please input exit   "<<endl;
        cout<<"PTCMS>>";cin>>inputstring;

        if(inputstring == "manage")
        {
            Clear_Grapics();
            if(!checktag)
            {
                cout<<"Please type in the manager account and password" << endl;
                string account; cout<<"Account >>";cin>>account;
                string password;cout<<"Password>>";cin>>password;
                if(account == "admin" && password == "admin") checktag = 1;
            }
            if(!checktag)
            {
                cout<<"Wrong account or password, try again!"<<endl;
                Sleep(1000);
            }
            else 
            {
                checktag = 1;
                Clear_Grapics();
                cout<<"Welcome to PTCMS Manager Mode "<<endl;
                cout<<"For now, system has a total transportation line of "<<n<<endl;
                cout<<"Total metro lines are "<<metro_total<<" , and bus lines are "<<bus_total<<endl;
                cout<<endl;
                for(int i=1;i<=metro_total;i++)
                {
                    cout<<"Metro Line "<<i<<" have the total stations of "<<metrolist[i].Length()<<endl;
                    for(int j=1;j<=metrolist[i].Length();j++)
                    {
                        int tempnow,tempnext;
                        if(metrolist[i].GetElem(j,&tempnow)) cout<<tempnow;
                        metrolist[i].NextElem(tempnow,&tempnext);
                        if(station[tempnow].iscross) cout<<"(cross)";
                        if(j<(metrolist[i].Length()))
                        {
                            Set_Color(4);
                            cout<<"<-"
                            ;int tempdis = find_edge_dis(tempnow,tempnext);
                            cout<<tempdis<<"->";
                            Set_Color(7);
                        }
                    }
                    cout<<endl;
                }

                for(int i=1;i<=bus_total;i++)
                {
                    cout<<"Bus Line "<<i<<" have the total stations of "<<buslist[i].Length()<<endl;
                    for(int j=1;j<=buslist[i].Length();j++)
                    {
                        int tempnow,tempnext;
                        if(buslist[i].GetElem(j,&tempnow)) cout<<tempnow;
                        buslist[i].NextElem(tempnow,&tempnext);
                        if(station[tempnow].iscross) cout<<"(cross)";
                        if(j<(buslist[i].Length()))
                        {
                            Set_Color(4);
                            cout<<"<-"
                            ;int tempdis = find_edge_dis(tempnow,tempnext);
                            cout<<tempdis<<"->";
                            Set_Color(7);
                        }
                    }
                    cout<<endl;
                }

                cout<<"If you want to add     station, input add"<<endl;
                cout<<"If you want to delete  station, input delete"<<endl;
                cout<<"If you want to exit management, input exit"<<endl;
                cout<<endl<<"PTCMS>>";cin>>inputstring;
                
                if(inputstring == "add")
                {
                    cout<<"Please type in the line and the station you want to add following the layout below"<<endl;
                    cout<<"(type:bus or metro) (line:1 or 2 or etc) (start point number) (station number) (distance)"<<endl;
                    cout<<"You can only use the number  "<<n+1<<endl;
                    cout<<endl<<"PTCMS>>";string type;int linep,startp,endp,disp;cin>>type>>linep>>startp>>endp>>disp;
                    if(endp<=n||(type != "metro"&&type != "bus"))
                    {
                        cout<<"Type or end point station error!";
                        Sleep(1000);
                        continue;
                    }
                    if(type == "metro")
                    {
                        int postemp=metrolist[linep].LocateElem(startp);
                        if(!postemp)  cout<<"Start point station error!"<<endl;
                        else{
                            metrolist[linep].Insert(postemp+1,endp);
                            add_edge(startp,endp,disp,(int)(disp/2));
                            add_edge(endp,startp,disp,(int)(disp/2));
                            station[endp].metroline_num[linep]=1;
                            n++;                          
                        }
                        cout<<"Add point from "<<startp<<" to "<<endp<<" successfully"<<endl;
                    }
                    else if(type == "bus")
                    {
                        int postemp=buslist[linep].LocateElem(startp);
                        if(!postemp)   cout<<"Start point station error!"<<endl;
                        else
                        {
                            buslist[linep].Insert(postemp+1,endp);
                            add_edge(startp,endp,disp,1);
                            add_edge(endp,startp,disp,1);
                            station[endp].busline_num[linep]=1;     
                            n++;     
                        }    
                        cout<<"Add point from"<<startp<<" to "<<endp<<" successfully"<<endl;         
                    }
                   
                }
                else if(inputstring == "delete")
                {
                    cout<<"Please type in the station you want delete from 1 to "<<n<<endl;
                    int delesta;cout<<"PTCMS>>";cin>>delesta;
                    if(station[delesta].iscross)
                    {
                        cout<<"Not Support for delete cross station for now!"<<endl;
                        Sleep(1000);
                    }
                    else
                    {  
                        int prepoint=0, afterpoint=0;
                        for(int i=1;i<=bus_total;i++)
                        {
                            if(station[delesta].busline_num[i])
                            {
                                buslist[i].PriorElem(delesta, &prepoint);
                                buslist[i].NextElem (delesta,&afterpoint);
                            }
                        }
                        for(int i=1;i<=metro_total;i++)
                        {
                            if(station[delesta].metroline_num[i])
                            {
                                metrolist[i].PriorElem(delesta, &prepoint);
                                metrolist[i].NextElem (delesta,&afterpoint);
                            }
                        }
                        int edge1 = find_edge(prepoint,delesta);
                        int edge2 = find_edge(afterpoint,delesta);
                        int dis1  = find_edge_dis(prepoint,delesta);
                        int dis2  = find_edge_dis(afterpoint,delesta);
                        delete_edge(edge1);
                        delete_edge(edge2);
                        if(station[delesta].busline_num[0] )
                        {
                            add_edge(prepoint,afterpoint,dis1+dis2-1,2);
                            add_edge(afterpoint,prepoint,dis1+dis2-1,2);
                        }
                        if(station[delesta].metroline_num[0] )
                        {
                            add_edge(prepoint,afterpoint,dis1+dis2-1,(int)(min(dis1,dis2)));
                            add_edge(afterpoint,prepoint,dis1+dis2-1,(int)(min(dis1,dis2)));
                        }
                    }
                    for(int i=1;i<=metro_total;i++)
                    {
                        int tempnum=metrolist[i].LocateElem(delesta);
                        if(tempnum) metrolist[i].Delete(tempnum,&delesta);
                    }
                    for(int i=1;i<=bus_total;i++)
                    {
                        int tempnum=buslist[i].LocateElem(delesta);
                        if(tempnum) buslist[i].Delete(tempnum,&delesta);
                    }
                    //n--;
                    cout<<endl<<"Delete No."<<delesta<<" station successfully"<<endl;
                }
                while(1)
                {
                    cout<<endl;
                    cout<<"Type in 'continue' to exit this page and return to main page"<<endl;
                    cout<<"PTCMS>>";cin>>inputstring;
                    if(inputstring == "continue") break;
                }

            }
        }

        else if(inputstring == "inquire")
        {
            Clear_Grapics();
            cout<<"Welcome to PTCMS Inquiry Mode "<<endl<<endl;
            for(int i=1;i<=metro_total;i++)
            {
                cout<<"Metro Line "<<i<<": ";

                for(int j=1;j<=metrolist[i].Length();j++)
                {
                    int tempnow,tempnext;
                    if(metrolist[i].GetElem(j,&tempnow)) cout<<tempnow;
                    metrolist[i].NextElem(tempnow,&tempnext);
                    if(station[tempnow].iscross) cout<<"(cross)";
                    if(j<(metrolist[i].Length()))
                    {
                        Set_Color(4);
                        cout<<"<--"
                        ;int tempdis = find_edge_dis(tempnow,tempnext);
                        cout<<tempdis<<"-->";
                        Set_Color(7);
                    }
                }
                cout<<endl<<endl;
            }
            for(int i=1;i<=bus_total;i++)
            {
                cout<<"Bus   Line "<<i<<": ";
                for(int j=1;j<=buslist[i].Length();j++)
                {
                    int tempnow,tempnext;
                    if(buslist[i].GetElem(j,&tempnow)) cout<<tempnow;
                    buslist[i].NextElem(tempnow,&tempnext);
                    if(station[tempnow].iscross) cout<<"(cross)";
                    if(j<(buslist[i].Length()))
                    {
                        Set_Color(4);
                        cout<<"<--"
                        ;int tempdis = find_edge_dis(tempnow,tempnext);
                        cout<<tempdis<<"-->";
                        Set_Color(7);
                    }
                }
                cout<<endl<<endl;
            }

            int startpoint,endpoint; // for searchtype: 1 for short route; 2 for least station; 3 for least money


            Set_Color(1);
            printf("============================= Search Mode ==============================\n");
	        printf("| Short Distance First:1 | Least Station First:2 | Least Money First:3 |\n");
	        printf("========================================================================\n");

            printf("============================ Choose Point ==============================\n");
	        printf("|              Start Point         |            End Point              |\n");
	        printf("========================================================================\n");

            cout<<endl<<endl;
            Set_Color(7);
            cout<<"Please type in your search mode"<<endl;
            cout<<endl<<"PTCMS>>";
            cin>>searchtype;
            if(searchtype != 1 && searchtype!=2 && searchtype!=3)
            {
                cout<<"Wrong searchtype. Please check";
                Sleep(1000);
                continue;
            }
            cout<<"Please type in your startpoint and endpoint from No.1 to No."<<n<<endl;
            cout<<endl<<"PTCMS>>";
            cin>>startpoint>>endpoint;

            cout<<endl;
            
            s=startpoint;
            for(int i=1;i<=n;i++) dis[i]=INF,path[i]=1;
            dijkstra();
            if(dis[endpoint] != INF )
            {
                if(searchtype == 1) cout<<"The short distance from No."<<startpoint<<" to No."<<endpoint<<" is "<<dis[endpoint]<<" km"<<endl;
                if(searchtype == 2) cout<<"The least station from No."<<startpoint<<" to No."<<endpoint<<" is "<<dis[endpoint]<<" stations"<<endl;
                if(searchtype == 3) cout<<"The least Money from No."<<startpoint<<" to No."<<endpoint<<" is "<<dis[endpoint]<<" yuan"<<endl;
                cout<<endl<<"Route: ";find(startpoint,endpoint);
                cout<<endl;
            }

            else cout<<"No access route, Sorry"<<endl;
            
            cout<<endl;
            while(1)
            {
                cout<<"Type in continue to exit this page and return to main page"<<endl;
                cout<<"PTCMS>>";cin>>inputstring;
                if(inputstring == "continue") break;
            }
        }
        else if(inputstring == "exit")
        {
            break;
        }
    }
    return 0;
}
